package br.uece.comp.heap.binario;

public class HeapBinario<E> {

	private E[] arranjo;

	public static final int PRIMEIRO_ELEMENTO = 0;

	private int qtdElementos = 0;

	/**
	 * Construtor do
	 */
	public HeapBinario(E[] arranjo) {
		this.arranjo = arranjo;
		qtdElementos = arranjo.length;

		/*for (int i = 0; arranjo[i] != null; i++) {
			this.qtdElementos++;
		}*/
		construirHEAP();
	}

	public E extrairMin() {
		E min = arranjo[PRIMEIRO_ELEMENTO];

		arranjo[PRIMEIRO_ELEMENTO] = arranjo[qtdElementos - 1];
		ajustarHEAP(PRIMEIRO_ELEMENTO);
		qtdElementos--;
		return min;
	}

	private void construirHEAP() {
		for (int i = qtdElementos - 1; i >= 0; i--) {
			ajustarHEAP(i);
		}
	}

	@SuppressWarnings("unchecked")
	private void ajustarHEAP(int i) {
		int menor = i;
		int esquerdo = esquerdo(i);
		int direito = direito(i);

		if (esquerdo <= qtdElementos - 1
				&& ehMenor((Comparable<E>) arranjo[esquerdo], arranjo[menor])) {
			menor = esquerdo;
		}
		if (direito <= qtdElementos - 1
				&& ehMenor((Comparable<E>) arranjo[direito], arranjo[menor])) {
			menor = direito;
		}
		if (menor != i) {
			E temp;
			temp = arranjo[i];
			arranjo[i] = arranjo[menor];
			arranjo[menor] = temp;
			ajustarHEAP(menor); // que n�o � mais o menor.
		}
	}

	@SuppressWarnings("unchecked")
	public void inserir(E elemento) {
		qtdElementos++;
		int i = qtdElementos - 1;
		arranjo[i] = elemento;

		while (i > 0 && ehMenor((Comparable<E>) arranjo[i], arranjo[pai(i)])) {
			E temp;
			temp = arranjo[i];
			arranjo[i] = arranjo[pai(i)];
			arranjo[pai(i)] = temp;

			i = pai(i);
		}
	}

	public static int esquerdo(int i) {
		return (2 * i) + 1;
	}

	public static int direito(int i) {
		return (2 * i) + 2;
	}

	public static int pai(int i) {
		return (i - 1) / 2;
	}

	private boolean ehMenor(Comparable<E> a, E b) {
		return a.compareTo(b) > 0;
	}

	public boolean isVazio() {
		return (qtdElementos == 0);
	}
}
